package com.leetcode.LC_MED;

import java.util.Arrays;

public class LC1552 {
    public int maxDistance(int[] position, int m) {

        Arrays.sort(position);
        if (m == 2) {
            return position[position.length - 1] - position[0];
        }
        int b = (position[position.length - 1] - position[0]) / (m - 1), a = 1;
        int ans = 1;
        while (a <= b) {
            int mid = a + (b - a) / 2;
            if (toCheck(position, m, mid)) {
                ans = mid;
                a=mid+1;
            } else {
                b=mid-1;
            }
        }
        return ans;
    }

    boolean toCheck(int[] position, int m, int mid) {
        int count = 1;
        int tmp = 0;
        for (int i = 1; i < position.length; i++) {
            if (position[i] - position[tmp] >= mid) {
                tmp = i;
                count++;
            }
        }
        return count >= m;
    }
}
